package 极客算法训练营.chapter10;

import java.util.ArrayDeque;
import java.util.Deque;

public class 跳跃游戏 {
    class Solution1 {
        private int maxDepth = 0;
        public boolean canJump(int[] nums) {
            int len = nums.length;
            boolean[] reachable = new boolean[len];//判断当前结点是否可以直达底部
            for (int i = 0; i < len; i++) {
                if (nums[i] >= len - 1 - i) {
                    reachable[i] = true;
                }
            }

            dfs(0, nums, reachable);
            return maxDepth >= nums.length - 1 ? true : false;
        }

        public void dfs(int index, int[] nums, boolean[] reachable) {
            if (index >= nums.length - 1 || reachable[index]) {
                maxDepth = nums.length - 1;
                return;
            }

            int curNum = nums[index];
            maxDepth = Math.max(maxDepth, index + curNum);
            for (int i = 1; i <= curNum; i++) {
                int nextNum = index + i;
                dfs(nextNum, nums, reachable);
            }
        }
    }

    class Solution2 {
        public boolean canJump(int[] nums) {
            if (nums == null || nums.length < 2) {
                return true;
            }
            int len = nums.length;
            boolean[] visited = new boolean[len];

            Deque<Integer> deque = new ArrayDeque<>();
            deque.add(0);
            visited[0] = true;

            while (!deque.isEmpty()) {
                int size = deque.size();
                for (int i = 0; i < size; i++) {
                    Integer poll = deque.poll();
                    if (poll + nums[poll] >= len - 1) return true;
                    for (int j = 1; j <= nums[poll]; j++) {
                        int nextNum = poll + j;
                        if (!visited[nextNum]) {
                            deque.add(nextNum);
                        }
                    }
                }
            }
            return false;
        }
    }

    class Solution {
        public boolean canJump(int[] nums) {
            int farthest = 0;
            for (int i = 0; i < nums.length; i++) {
                if (farthest >= nums.length - 1) return true;
                if (i <= farthest) {
                    farthest = Math.max(i + nums[i], farthest);
                }
            }
            return false;
        }
    }
}
